<!DOCTYPE html>
<html lang="en-US" class="no-js jetpack-lazy-images-js-enabled">

<head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

    <meta name="viewport" content="width=device-width, initial-scale=1">

    <title>Personal Blog By Alen Andry</title>

    <meta name="application-name" content="alenblog">

    <link rel="stylesheet" href="./idex_files/ais8cmj.css">

    <link rel="stylesheet" href="./idex_files/style.css">

    <link rel="shortcut icon" href="./google.svg">


    <!-- This site is optimized with the Yoast SEO Premium plugin v14.9 - https://yoast.com/wordpress/plugins/seo/ -->
    <meta name="description" content="A live podcast about front end web design and UX.">
    <meta name="robots" content="index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1">
    <link rel="canonical" href="https://shoptalkshow.com/">
    <link rel="next" href="https://shoptalkshow.com/page/2/">
    <meta property="og:locale" content="en_US">
    <meta property="og:type" content="website">
    <meta property="og:title" content="ShopTalk Show">
    <meta property="og:description" content="A podcast about building websites.">
    <meta property="og:url" content="https://shoptalkshow.com/">
    <meta property="og:site_name" content="ShopTalk">
    <meta property="og:image"
        content="https://i2.wp.com/shoptalkshow.com/wp-content/uploads/2020/03/default-graphic.png?fit=552%2C552&amp;ssl=1">
    <meta property="og:image:width" content="552">
    <meta property="og:image:height" content="552">
    <meta name="twitter:card" content="summary">
    <meta name="twitter:site" content="@shoptalkshow">
    <script type="text/javascript" async="" src="./idex_files/ga.js"></script>
    <script type="application/ld+json"
        class="yoast-schema-graph">{"@context":"https://schema.org","@graph":[{"@type":"WebSite","@id":"https://shoptalkshow.com/#website","url":"https://shoptalkshow.com/","name":"ShopTalk","description":"A live podcast about front end web design and UX.","potentialAction":[{"@type":"SearchAction","target":"https://shoptalkshow.com/?s={search_term_string}","query-input":"required name=search_term_string"}],"inLanguage":"en-US"},{"@type":"CollectionPage","@id":"https://shoptalkshow.com/#webpage","url":"https://shoptalkshow.com/","name":"ShopTalk: A Web Design and Development Podcast with Chris Coyier and Dave Rupert","isPartOf":{"@id":"https://shoptalkshow.com/#website"},"description":"A live podcast about front end web design and UX.","inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https://shoptalkshow.com/"]}]}]}</script>
    <!-- / Yoast SEO Premium plugin. -->


    <link rel="dns-prefetch" href="https://s.w.org/">
    <link rel="dns-prefetch" href="https://c0.wp.com/">
    <link rel="dns-prefetch" href="https://i0.wp.com/">
    <link rel="dns-prefetch" href="https://i1.wp.com/">
    <link rel="dns-prefetch" href="https://i2.wp.com/">
    <script type="text/javascript">
        window._wpemojiSettings = { "baseUrl": "https:\/\/s.w.org\/images\/core\/emoji\/13.0.0\/72x72\/", "ext": ".png", "svgUrl": "https:\/\/s.w.org\/images\/core\/emoji\/13.0.0\/svg\/", "svgExt": ".svg", "source": { "concatemoji": "https:\/\/shoptalkshow.com\/wp-includes\/js\/wp-emoji-release.min.js?ver=5.5.2" } };
        !function (e, a, t) { var r, n, o, i, p = a.createElement("canvas"), s = p.getContext && p.getContext("2d"); function c(e, t) { var a = String.fromCharCode; s.clearRect(0, 0, p.width, p.height), s.fillText(a.apply(this, e), 0, 0); var r = p.toDataURL(); return s.clearRect(0, 0, p.width, p.height), s.fillText(a.apply(this, t), 0, 0), r === p.toDataURL() } function l(e) { if (!s || !s.fillText) return !1; switch (s.textBaseline = "top", s.font = "600 32px Arial", e) { case "flag": return !c([127987, 65039, 8205, 9895, 65039], [127987, 65039, 8203, 9895, 65039]) && (!c([55356, 56826, 55356, 56819], [55356, 56826, 8203, 55356, 56819]) && !c([55356, 57332, 56128, 56423, 56128, 56418, 56128, 56421, 56128, 56430, 56128, 56423, 56128, 56447], [55356, 57332, 8203, 56128, 56423, 8203, 56128, 56418, 8203, 56128, 56421, 8203, 56128, 56430, 8203, 56128, 56423, 8203, 56128, 56447])); case "emoji": return !c([55357, 56424, 8205, 55356, 57212], [55357, 56424, 8203, 55356, 57212]) }return !1 } function d(e) { var t = a.createElement("script"); t.src = e, t.defer = t.type = "text/javascript", a.getElementsByTagName("head")[0].appendChild(t) } for (i = Array("flag", "emoji"), t.supports = { everything: !0, everythingExceptFlag: !0 }, o = 0; o < i.length; o++)t.supports[i[o]] = l(i[o]), t.supports.everything = t.supports.everything && t.supports[i[o]], "flag" !== i[o] && (t.supports.everythingExceptFlag = t.supports.everythingExceptFlag && t.supports[i[o]]); t.supports.everythingExceptFlag = t.supports.everythingExceptFlag && !t.supports.flag, t.DOMReady = !1, t.readyCallback = function () { t.DOMReady = !0 }, t.supports.everything || (n = function () { t.readyCallback() }, a.addEventListener ? (a.addEventListener("DOMContentLoaded", n, !1), e.addEventListener("load", n, !1)) : (e.attachEvent("onload", n), a.attachEvent("onreadystatechange", function () { "complete" === a.readyState && t.readyCallback() })), (r = t.source || {}).concatemoji ? d(r.concatemoji) : r.wpemoji && r.twemoji && (d(r.twemoji), d(r.wpemoji))) }(window, document, window._wpemojiSettings);
    </script>
    <script src="./idex_files/wp-emoji-release.min.js" type="text/javascript" defer=""></script>
    <style type="text/css">
        .word pre {
            font-size: 2.5rem;
            padding: auto, 10;
            margin-top: 0.5rem;
            margin-left: 0.5rem;
        }

        img.wp-smiley,
        img.emoji {
            display: inline !important;
            border: none !important;
            box-shadow: none !important;
            height: 1em !important;
            width: 1em !important;
            margin: 0 .07em !important;
            vertical-align: -0.1em !important;
            background: none !important;
            padding: 0 !important;
        }
    </style>
    <link rel="stylesheet" id="wp-block-library-css" href="./idex_files/style.min.css" type="text/css" media="all">
    <link rel="stylesheet" href="./idex_files/code.css">
    <style id="wp-block-library-inline-css" type="text/css">
        .has-text-align-justify {
            text-align: justify;
        }
    </style>
    <link rel="stylesheet" id="jetpack_css-css" href="./idex_files/jetpack.css" type="text/css" media="all">
    <link rel="https://api.w.org/" href="https://shoptalkshow.com/wp-json/">
    <link rel="EditURI" type="application/rsd+xml" title="RSD" href="https://shoptalkshow.com/xmlrpc.php?rsd">
    <link rel="wlwmanifest" type="application/wlwmanifest+xml"
        href="https://shoptalkshow.com/wp-includes/wlwmanifest.xml">
    <meta name="generator" content="WordPress 5.5.2">
    <style type="text/css">
        img#wpstats {
            display: none
        }
    </style>
    <style type="text/css">
        /* If html does not have either class, do not show lazy loaded images. */
        html:not(.jetpack-lazy-images-js-enabled):not(.js) .jetpack-lazy-image {
            display: none;
        }
    </style>
    <script>
        document.documentElement.classList.add(
            'jetpack-lazy-images-js-enabled'
        );
    </script>

    <script>
        var _gaq = _gaq || [];
        _gaq.push(['_setAccount', 'UA-2419836-8']);
        _gaq.push(['_trackPageview']);

        (function () {
            var ga = document.createElement('script');
            ga.type = 'text/javascript';
            ga.async = true;
            ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
            var s = document.getElementsByTagName('script')[0];
            s.parentNode.insertBefore(ga, s);
        })();
    </script>

</head>

<body class="home blog">

    <header class="site-header">

        <div class="logo-and-tagline">
            <h1><a href="https://alenandry.github.io">Alen's Blog</a></h1>
            <p>西电儿的个人博客</p>
        </div>

        <nav id="main-nav" class="main-nav mobile-is-closed">
            <button aria-expanded="false" id="menu-button" class="menu-button">Menu</button>
            <ul>
                <li class="main-nav-episodes"><a href="./rust.html">Rust开发</a></li>
                <li class="main-nav-series"><a href="./houduan.html">web后端开发</a></li>
                <li class="main-nav-advertising"><a href="./fontend.html">前端机器学习教程</a></li>
                <li class="main-nav-ask"><a href="./javascript">javascript数据结构</a></li>
                <li class="main-nav-topics"><a href="./python.html">python数据结构</a></li>
                <li class="main-nav-topics"><a href="./java.html">java数据结构</a></li>
                <li class="main-nav-ask"><a href="./vue.html">Vue开发</a></li>
                <li class="main-nav-ask"><a href="./react.html">React开发</a></li>
                <li class="main-nav-ask"><a href="./xiaochnegxu.html">小程序开发</a></li>

            </ul>
        </nav>
        <form role="search" method="get" id="searchform" class="searchform" action="./index.html">
            <div>
                <label for="s">Search for:</label>
                <input type="text" value="" name="s" id="s">
                <input type="submit" id="searchsubmit" value="Search">
            </div>
        </form>
    </header>
    <main class="post">
        <h2>基于哈夫曼编码的压缩算法的Python实现</h2>

        <article>
            <h3>1.背景</h3>
            <div class="content">
                <span>
                    离散数学老师布置了一份大作业，作业题目就是用自己喜欢的编程语言来实现课上所学的哈夫曼编码算法（Huffman
                    Coding）。哈夫曼编码是一种采用变长编码表来表示数据的编码方式。其详细介绍详见下方引自维基百科的引文。
                </span>
                <pre>
                    <code class=Python>
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，</br>其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，</br>反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，</br>从而达到无损压缩数据的目的。
                    </code>
                </pre>
                <h3>2.哈夫曼树及哈夫曼编码</h3>
                <span>
                    哈夫曼编码基于哈夫曼树(Huffman Tree)来实现，哈夫曼树是将符号出现的频率作为叶子的权值所构建一棵二叉树。我们以一个例子来详细解释哈夫曼树。

                    有这么一句话：“This is a test str”
                </span>
                <img src="./idex_files/images/haff.png" alt="">
                <h3>
                    3.基于哈夫曼编码的压缩算法的Python实现
                </h3>
                <pre>
                <code class="Python">
class node(object):

def __init__(self,value = None,left = None,right = None,father = None):
self.value = value
self.left = left
self.right = right
self.father = father

def build_father(left,right):
n = node(value = left.value + right.value,left = left,right = right)
left.father = right.father = n
return n

def encode(n):
if n.father == None:
return b''
if n.father.left == n:
return node.encode(n.father) + b'0' #左节点编号'0'
else:
return node.encode(n.father) + b'1' #右节点编号'1'
                </code>
            </pre>
                <h3>
                    3.2 构建哈夫曼树
                </h3>
                <span>
                    由于哈夫曼编码的过程中有许多步骤重复执行，因此在节点类的基础上，借助递归的思想来完成哈夫曼树的构建。

                </span>
                <pre>
                <code class="Python">
def build_tree(l):

if len(l) == 1:
return l
sorts = sorted(l,key = lambda x:x.value,reverse = False)
n = node.build_father(sorts[0],sorts[1])
sorts.pop(0)
sorts.pop(0)
sorts.append(n)
return build_tree(sorts)
                </code>
            </pre>
                <h3>
                    3.3 利用构建好的哈夫曼树进行编码
                </h3>
                <pre>
                <code class="Python">
def encode(echo):

for x in node_dict.keys():
ec_dict[x] = node.encode(node_dict[x])
if echo == True: #输出编码表（用于调试）
print(x)
print(ec_dict[x])
                </code>
            </pre>
                <h3>
                    3.4 实现文件压缩、解压函数

                </h3>
                <span>
                    既然我们实现的是压缩算法，那么就必须能够实现文件的压缩、解压操作才有意义。如果只能实现字符串的编码或者压缩解压，是没有很大的实用价值的。
                </span>
                <pre>
                <code class="Python">
def encodefile(file):

print("Starting encode...")
f = open(file,"rb")
bytes_width = 1 #每次读取的字节宽度
i = 0

f.seek(0,2)
count = f.tell() / bytes_width
print(count)
nodes = [] #结点列表，用于构建哈夫曼树
buff = [b''] * int(count)
f.seek(0)

#计算字符频率,并将单个字符构建成单一节点
while i < count: buff[i]=f.read(bytes_width) if count_dict.get(buff[i], -1)==-1: count_dict[buff[i]]=0
    count_dict[buff[i]]=count_dict[buff[i]] + 1 i=i + 1 print("Read OK") print(count_dict) for x in count_dict.keys():
    node_dict[x]=node(count_dict[x]) nodes.append(node_dict[x]) f.close() tree=build_tree(nodes) #哈夫曼树构建 encode(False)
    #构建编码表 print("Encode OK") head=sorted(count_dict.items(),key=lambda x:x[1] ,reverse=True) bit_width=1
    print("head:",head[0][1]) #动态调整编码表的字节长度，优化文件头大小 if head[0][1]> 255:
    bit_width = 2
    if head[0][1] > 65535:
    bit_width = 3
    if head[0][1] > 16777215:
    bit_width = 4
    print("bit_width:",bit_width)
    i = 0
    raw = 0b1
    last = 0
    name = file.split('.')
    o = open(name[0]+".ys" , 'wb')
    o.write(int.to_bytes(len(ec_dict) ,2 ,byteorder = 'big')) #写出结点数量
    o.write(int.to_bytes(bit_width ,1 ,byteorder = 'big')) #写出编码表字节宽度
    for x in ec_dict.keys(): #编码文件头
    o.write(x)
    o.write(int.to_bytes(count_dict[x] ,bit_width ,byteorder = 'big'))

    print('head OK')
    while i < count: #开始压缩数据 for x in ec_dict[buff[i]]: raw=raw << 1 if x==49: raw=raw | 1 if raw.bit_length()==9:
        raw=raw & (~(1 << 8)) o.write(int.to_bytes(raw ,1 , byteorder='big' )) o.flush() raw=0b1 tem=int(i /len(buff) *
        100) if tem> last:
        print("encode:", tem ,'%') #输出压缩进度
        last = tem
        i = i + 1

        if raw.bit_length() > 1: #处理文件尾部不足一个字节的数据
        raw = raw << (8 - (raw.bit_length() - 1)) raw=raw & (~(1 << raw.bit_length() - 1)) o.write(int.to_bytes(raw ,1 ,
            byteorder='big' )) o.close() print("File encode successful.")
                </code>
            </pre>
                <p>解压文件：</p>
                <pre>
                <code class="Python">
def decodefile(inputfile, outputfile):

print("Starting decode...")
count = 0
raw = 0
last = 0
f = open(inputfile ,'rb')
o = open(outputfile ,'wb')
f.seek(0,2)
eof = f.tell()
f.seek(0)
count = int.from_bytes(f.read(2), byteorder = 'big') #取出结点数量
bit_width = int.from_bytes(f.read(1), byteorder = 'big') #取出编码表字宽
i = 0
de_dict = {}
while i < count: #解析文件头 key=f.read(1) value=int.from_bytes(f.read(bit_width), byteorder='big' ) de_dict[key]=value i=i +
    1 for x in de_dict.keys(): node_dict[x]=node(de_dict[x]) nodes.append(node_dict[x]) tree=build_tree(nodes) #重建哈夫曼树
    encode(False) #建立编码表 for x in ec_dict.keys(): #反向字典构建 inverse_dict[ec_dict[x]]=x i=f.tell() data=b'' while i < eof:
    #开始解压数据 raw=int.from_bytes(f.read(1), byteorder='big' ) # print("raw:",raw) i=i + 1 j=8 while j> 0:
    if (raw >> (j - 1)) & 1 == 1:
    data = data + b'1'
    raw = raw & (~(1 << (j - 1))) else: data=data + b'0' raw=raw & (~(1 << (j - 1))) if inverse_dict.get(data, 0) !=0:
        o.write(inverse_dict[data]) o.flush() #print("decode",data,":",inverse_dict[data]) data=b'' j=j - 1 tem=int(i /
        eof * 100) if tem> last:
        print("decode:", tem,'%') #输出解压进度
        last = tem
        raw = 0

        f.close()
        o.close()
        print("File decode successful.")
                </code>
            </pre>
                <h3>
                    3.4 测试效果

                </h3>
                <span>
                    完成后，我使用各种类型的文件进行测试，测试效果如下：
                </span>
                <img src="./idex_files/images/com.png" alt="">

            </div>
        </article>

    </main>


    <footer class="site-footer">

        <div class="apply-typography">
            <p>
                Alen Andry 的博客
            </p>

            <a href="./index.html" class="twitter-follow-button">Blog</a>

            <a href="https://github.com/alenandry">Github</a>

            <a href="https://juejin.cn/user/3993068510655703">掘金链接</a>

            <a href="dnrops@outlook.com">联系邮箱：dnrops@outlook.com</a>
        </div>
    </footer>

    <script type="text/javascript" src="./idex_files/photon.min.js" id="jetpack-photon-js"></script>
    <script type="text/javascript" src="./idex_files/lazy-images.min.js" id="jetpack-lazy-images-js"></script>
    <script type="text/javascript" src="./idex_files/wp-embed.min.js" id="wp-embed-js"></script>
    <script type="text/javascript" src="./idex_files/e-202045.js" async="async" defer="defer"></script>
    <script type="text/javascript">
        _stq = window._stq || [];
        _stq.push(['view', { v: 'ext', j: '1:8.9.1', blog: '54408968', post: '0', tz: '-6', srv: 'shoptalkshow.com' }]);
        _stq.push(['clickTrackerInit', '54408968', '0']);
    </script>

    <script src="./idex_files/main.js"></script>
    <script src="./idex_files/code.js"></script>
    <script>hljs.highlightAll();</script>

</body>

</html>